|
課程名稱 |
資料結構與程式設計
Data Structure and Programming |
|
開課學期 |
107-1 |
|
授課對象 |
電機工程學系 |
|
授課教師 |
吳沛遠 |
|
課號 |
EE3011 |
|
課程識別碼 |
901 31900 |
|
班次 |
02 |
|
學分 |
3.0 |
|
全/半年 |
半年 |
|
必/選修 |
選修 |
|
上課時間 |
星期一7,8,9(14:20~17:20) |
|
上課地點 |
電二143 |
|
備註 |
總人數上限：80人 |
|
Ceiba 課程網頁 |
http://ceiba.ntu.edu.tw/1071EE3011_02 |
|
課程簡介影片 |
|
|
核心能力關聯 |
核心能力與課程規劃關聯圖 |
|
課程大綱
|
|
為確保您我的權利,請尊重智慧財產權及不得非法影印
|
|
課程概述 |
In this course you will learn the most important algorithms and data structures in both theory as well as their realization with Python. The topics include but not limited to
1. Programming in Python: The built-in data types and Numpy package.
2. Measure the qualities of data structures and algorithms by time and space.
3. Linear data structures: stack, linked list, queue
4. Sorting: bubble sort, heap sort, merge sort, quicksort, radix sort
5. Trees for sublinear search time: Binary Search Trees, red-black trees, AVL Tree
6. Heap realization of priority queue: Binary heap, binomial heap, and Fibonacci heap.
7. Graph algorithms: search, minimum spanning trees, shortest paths |
|
課程目標 |
1. Understanding the strength and weakness of various data structures.
2. Understanding how to implement time and memory efficient Python codes by choosing the appropriate data structures.
3. Understanding the most important searching, sorting, and graph-based algorithms. |
|
課程要求 |
Prerequisites: Familiarity with at least one object oriented programming language (C++, Java, Python, etc…) |
|
預期每週課後學習時數 |
|
|
Office Hours |
|
|
指定閱讀 |
待補 |
|
參考書目 |
1. R. Sedgewick & K. Wayne, Algorithms, 4th edition
2. B. Miller, D. Ranum, and Luther College, Problem Solving with Algorithms and Data Structures using Python (e-book)
http://interactivepython.org/runestone/static/pythonds/index.html |
|
評量方式
(僅供參考) |
|
No. |
項目 |
百分比 |
說明 |
|
1. |
Written Assignments |
15% |
|
2. |
Programming Assignments |
25% |
|
3. |
Midterm exam |
30% |
|
4. |
Final exam |
30% |
|
|
|
週次 |
日期 |
單元主題 |
|
第1週 |
09/10 |
Syllabus and Introduction |
|
第2週 |
09/17 |
Complexity Analysis - Part I: Big-Oh Notations |
|
第3週 |
09/24 |
Moon Festival Holiday |
|
第4週 |
10/01 |
Complexity Analysis - Part II: Properties and algorithm analysis |
|
第5週 |
10/08 |
Linear Data Structure: Stack, queue, deque, ordered/unordered linked list |
|
第6週 |
10/15 |
Complexity Analysis - Part III: Master Theorem for recursion analysis
|
|
第7週 |
10/22 |
Recursion and Linear Programming |
|
第8週 |
10/29 |
Binary Tree; AVL Tree |
|
第9週 |
11/05 |
突發事件停課 |
|
第10週 |
11/12 |
Midterm Exam |
|
第11週 |
11/19 |
Splay Tree; 2-4 Tree |
|
第12週 |
11/26 |
Red Black Tree, AA Tree |
|
第13週 |
12/03 |
Hash, Binary Heap |
|
第14週 |
12/10 |
Binomial Heap, Fibonacci Heap |
|
第15週 |
12/17 |
Leftist Heap, Skew Heap, Sorting |
|
第15週 |
12/22 |
Disjoint Set |
|
第16週 |
12/24 |
Skip List |
|
第17週 |
01/07 |
Final Exam |
|